package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣中等103锯齿状层序遍历二叉树
 */
public class LevelOrder2 {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        if(root==null){
            return ans;
        }
        dfs2(root,0);
        return ans;
    }
    private void dfs2(TreeNode root,int level){
        if(root==null){
            return;
        }
        if(ans.size()==level){
            ans.add(new ArrayList<>());
        }
        //取当前层的结果
        List<Integer> tmp = ans.get(level);
        //注意此处要对level作加1操作
        if(((level+1)%2)==1){
            //奇数层，从左到右
            tmp.add(root.data);
        }else {
            //从右向左，要把后到的元素放到最左边，所以把每个后来的都放到最左边即可
            tmp.add(0,root.data);
        }
        if(root.left!=null){
            dfs2(root.left,level+1);
        }
        if(root.right!=null){
            dfs2(root.right,level+1);
        }
    }
}
